import java.util.HashMap;
import java.util.Map;

/**
 * 双指针
 * 给定已按升序排序的整数数组，找到两个数字，使它们相加到特定的目标数。
 * 函数twoSum应返回两个数字的索引，以便它们加起来到目标，其中index1必须小于index2。
 * 您返回的答案（index1和index2）不是从零开始的。
 * 您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。
 */
//三种方式
public class SumII {
//    第一种方式 时间复杂度O(nlogn)
    public static void sumII(int[] nums, int target) {
        int[] a=new int[3];
        int i=0;
        int j=nums.length-1;
        while(true){
            if(nums[i]+nums[j]==target){
                a[1]=i+1;
                a[2]=j+1;
                break;
            }else if(nums[i]+nums[j]>target){
                j--;
            }else if(nums[i]+nums[j]<target){
                i++;
            }
        }
        System.out.println(a[1]+"---"+a[2]);
    }

    //  第二种方式 时间复杂度O(2n)
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        int[] a = new int[2];
        for (int i = 0; i < nums.length; i++) {
            map.put(target - nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            //可能存在一个数x,满足x*2=target，i!=map.get(nums[i])可以避免
            if (map.containsKey(nums[i]) == true && i != map.get(nums[i])) {
                a[0] = i < map.get(nums[i]) ? i : map.get(nums[i]);
                a[1] = i > map.get(nums[i]) ? i : map.get(nums[i]);
                System.out.println(a[0] + "--" + a[1]);
                break;
            }
        }
        return a;
    }
//  第三种方式 时间复杂度O(n^2)
    public static void sumii(int[] nums,int target){
        int len=nums.length;
        int[] a=new int[2];
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                if(nums[i]+nums[j]==target){
                    a[0]=i;
                    a[1]=j;
                }
            }
        }
        System.out.println(a[0]+"------"+a[1]);
    }
    public static void main(String[] args) {
        int[] nums = {2, 3, 7, 11, 15};
        int target = 9;
        sumII(nums,target);
        System.out.println(twoSum(nums, target));
        sumii(nums,target);
    }
}
